package 单链表;
import java.util.ArrayList;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //测试
        //先创建节点
        HeroNode hero1 = new HeroNode(1,"宋江","及时雨");
        HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3 = new HeroNode(3,"吴用","智多星");
        HeroNode hero4 = new HeroNode(4,"林冲","豹子头");

        //创建单链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //加入
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero4);
        //显示一把
        singleLinkedList.list();

        //删除一个节点
        singleLinkedList.delete(1);
        System.out.println("删除链表后的情况");
        singleLinkedList.list();

        //测试一下求单链表中有效结点的个数
        System.out.println("有效的节点个数 = " + getLength(singleLinkedList.getHead()));

        //测试一下求单链表中倒数第 n 个节点
        check(1, singleLinkedList.getHead());
        System.out.println(findLastIndexNode(singleLinkedList.getHead(),4));

        //输出链表的长度
        System.out.println(getLength(singleLinkedList.getHead()));
        //singleLinkedList.add(hero1);
        singleLinkedList.list();          //这个链表的元素并不会自动消失，发现问题！！！！
        singleLinkedList.add(hero1);
        singleLinkedList.list();
    }

    //方法：获取到单链表的节点的个数（如果有带头节点的链表，需求不统计头结点）
    /**
     *
     * @param head 链表的头结点
     * @return 返回的是有效结点的个数
     * */

    public static int getLength(HeroNode head){
        HeroNode temp = head.next;
        if(head.next == null){
            System.out.println("该链表为空");
            return 0;
        }
        int i = 0;
        while (true){
            if(temp == null){
                break;
            }
            i++;
            temp = temp.next;       //如果初值是 head 这里写成temp.next = temp.next.next  无意中将节点删掉了一个，一定要谨慎，这里做
        }                           //赋值变换的时候
        return i;
    }

    //查找单链表中倒数第k个节点  , 这是我自己写的 ，说实话这叫面试题吗？？？？
    public static void check(int no,HeroNode head){  //嗯，说实话，还有很多细节需要处理
        HeroNode temp = head;
        int num = getLength(head);
        if(num == 0){
            System.out.println("此链表为空");
            return;
        }
        for(int i = 0;i <= num - no;i++){
            temp = temp.next;  // 我这里多了一次循环，因为我把temp的初值赋成了 head，而不是 head.next
        }
        System.out.println(temp);
    }
    //下面是老师写的这个方法
    //思路
    //1.编写一个方法，接收head节点，同时接收一个 index
    //index 表示的是 倒数第 index 个节点
    //2.先把链表从头到尾遍历，得到链表的总长度
    //3.得到 size 后，我们从链表的第一个开始遍历（size - index）个，就得到了结果，和我的思路一样
    //如果找到了，则返回这个节点，如果找不到，则返回null
    public static HeroNode findLastIndexNode(HeroNode head,int index){
        //判断如果链表为空，返回null
        if(head.next == null){
            return null; // 没有找到
        }
        //第一次遍历得到链表的长度
        int size = getLength(head);
        //第二次遍历,就是我们倒数第k个节点
        //先做一个index校验
        if(index <= 0 || index > size){
            return null;
        }
        //定义一个辅助变量,for循环定位到倒数的 index 个
        HeroNode cur = head.next;
        for(int i = 0;i < size - index;i++){
            cur = cur.next;
        }
        return cur;  // 将找到的头结点返回
    }
}

//定义SingleLinkedList 管理英雄的数据
class SingleLinkedList{
    //先初始化一个头节点，头结点不要动
    private HeroNode head = new HeroNode(0,"","");

    //返回一个head头结点
    public HeroNode getHead(){
        return head;
    }

    //添加节点到单项列表
    //思路，当不考虑编号顺序时
    //1.找到当前链表的最后节点
    //2.将最后这个节点的 next 指向新的节点
    public void add(HeroNode heroNode){
        //因为head节点不能动，因此我们需要一个辅助遍历 temp
        HeroNode temp = head; //如果你写成 temp = head.next 那么运行到下面 那么null.next是什么东西(假设该链表中没有任何数据而我正向里面加数据，就会出现这种情况)
        //遍历链表，找到最后    看看 Main1 类 你会找到答案的！！！！！！
        while(true){
            //找到链表的最后
            if(temp.next == null){
                break;
            }
            //如果没有找到最后，就将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next 指向新的节点
        temp.next = heroNode;  // 这才是真正将节点的信息进行赋值，抛开是否和本题有关，如果只写成 temp = heroNode
                               //这不会有任何的数据传递，因为你赋值给了一个引用，如果你赋值给了引用中的一个变量就可以改变了
    }

    //第二种方式再添加英雄时，根据排名将英雄插入指定的位置
    //将最后这个节点的的next指向新的节点（如果有这个排名，就添加失败，并给出提示）
    public void addByOrder(HeroNode heroNode){
        //因为头结点不能动，所以我们仍然通过一个辅助指针（变量）来帮助找到添加的位置
        //因为这是个单链表，因为我们找的temp是位于添加位置的前一个节点，否则将无法插入元素
        //因为你定义的next指向的是下一个节点  上面这句话很重要，必须要从第一个找所以temp的初值是head，所以temp是所找位置的上一个位置
        HeroNode temp = head;
        boolean flag = false;  //标志添加的编号是否存在，默认为false
                                //如果将temp的初值改变那么有可能temp的值并不是我们想要找到的位置
        while(true){
            if(temp.next == null){  //说明temp已经在链表的最后，在添加第一个数据时，就算输入的是对象的字段 no 是负数或是零也能保证加进去
                break;
            }//注意这两个if语句的先后顺序
            if(temp.next.no > heroNode.no){ //位置找到，就在temp的后面插入
                break;
            }else if(temp.next.no == heroNode.no){ //说明希望添加的heroNode的编号已经存在
                flag = true;  //说明编号已经存在
                break;
            }
            temp = temp.next;  //后移，遍历当前的链表
        }
        //判断flag的值
        if(flag){
            System.out.printf("准备插入的这个英雄的编号%d,不能加入\n",heroNode.no);
        }else{
            //插入到链表中
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //修改节点的信息，根据no编号修改，即no编号不能改
    //说明
    //1.根据 newHeroNode 的 no 来修改
    public void update(HeroNode newHeroNode){
        //判断是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        //找到需要修改的节点
        //先定义一个辅助变量
        HeroNode temp = head.next;  //初值是head.next理由应该是不能修改头结点？？
        boolean flag = false;  //表示是否找到该节点
        while(true){
            if(temp == null){
                break; //已经遍历完链表
            }
            if(temp.no == newHeroNode.no){
                //找到了
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag判断是否找到要修改的节点
        if(flag){
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        }else{ //没有找到
            System.out.printf("没有找到编号是%d的节点，不能修改\n",newHeroNode.no);
        }

    }

    //删除节点 下面这段代码是我写的，有问题
    /*public void delete(int no){
        HeroNode temp = head.next;               //头结点不动的话temp的初始值就是head而不是head.next
        boolean flag = false;                    //如果写成 temp = head的话
        if(head.next == null){
            System.out.println("此链表已为空");
            return;
        }
        while(true){
            if(temp == null){             //这就需要改为 temp.next == null
                break;
            }
            if(temp.no == no){         //这需要写成 temp.next.no == heroNode.no
                flag = true;
                break;
            }
            temp = temp.next;                   //这里就需要改为 temp.next = temp.next.next 这明显就很不合理，你把第二个元素
        }
        if(flag) {  //此时temp指向的是英雄一，那么下面这个代码就毫无意义，而且还错了，你让英雄1中的next指向了英雄一的next，你这不是闹着玩吗
                    //temp.next = heroNode.next
            temp = temp.next; //这又是什么，temp仅仅只是英雄1的对象引用，和英雄1的next并没有任何关联，仅仅是把英雄一的对象引用赋值给了英雄一
                                  //我的看法：temp此时的值已经被temp = temp.next;操纵过了所以它可以改变原传入数据的值
                                 //以上看法仅代表将一个引用传进来，会改变原方法中创建的引用
                                //我认为真正错的地方是因为，没有真正的改变节点中next的值，只是将
        }else{
            System.out.println("要删除的数据不存在！");
        }
    } */

    public void delete(int no){
        HeroNode temp = head;   //这里是为了能够找到待删除节点的前一个节点，temp的指向是指向待删除节点的前一个节点
        boolean flag = false;
        while(true){
            if(temp.next == null){
                break;
            }
            if(temp.next.no == no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            temp.next = temp.next.next;  //改变了HeroNode中的next变量，真正的将数据连接起来
        }else{                           //而上面那个代码就仅仅改变了temp变量的值，这里所涉及的知识点，两个引用同时指向一个对象，并且通过辅助变量改变其中的next变量
            System.out.println("该数组不存在这样的数据");
        }
    }

    //显示链表【遍历】
    public void list(){
        //判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        //因为头结点不能动，因此我们需要一个辅助变量来遍历
        HeroNode temp = head.next; //因为是遍历所以用next判断，并且在上面还有判断head.next是否为空指针的判断
        while(true) {     //这里把temp的初值定为head也没啥问题，然后再向下改
            if (temp == null) {  //因为是打印所以不用temp.next == null 做判断条件
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将temp后移，一定要后移
            temp = temp.next;
        }
        //System.out.println(head.next);  当我把这段代码加上时，会输出头结点所对应的第一个节点的元素，嗯看来我得研究一下这个问题了
    }
}

//定义一个HeroNode，每一个对象就是一个节点
class HeroNode{
    public int no;  //编号
    public String name;
    public String nickName;
    public HeroNode next; //指向下一个节点
    //构造器
    public HeroNode(int hNo,String hName,String hNickname){
        this.no = hNo;
        this.name = hName;
        this.nickName = hNickname;
    }

    //为了显示方法，我们重新编写toString方法
    public String toString(){
        return "HeroNode [no=" + no + ", name=" + name + ", nickName="+nickName + "]";
    }
}
